package com.hanxiaozhang.no3algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 〈一句话功能简述〉<br>
 * 〈二叉树〉
 *
 * @author hanxinghua
 * @create 2020/5/23
 * @since 1.0.0
 */
public class No2BinaryBree {


    /**
     * 二叉树形状：
     * ----------1
     * -------/    \
     * ------2      3
     * ----/  \   /  \
     * ---4    5 6    7
     *
     * @param args
     */
    public static void main(String[] args) {

        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        // 基础知识点：先、中、后遍历
        // iterate(head);

        // 按层遍历
        // layer(head);

        // 按层序列化
        Queue<Integer> results = serializeByLayer(head);
        System.out.println(results);

        // 按层反序列化
        Node layer = deserializeByLayer(results);

    }


    /**
     * 按层遍历反序列化
     *
     * @param queues
     * @return
     */
    private static Node deserializeByLayer(Queue<Integer> queues) {

        if (queues == null || queues.isEmpty() || queues.peek() == null) {
            return null;
        }
        // 构建头结点
        Node head = generateNode(queues.poll());
        // 临时队列
        Queue<Node> helpQueue = new LinkedList<>();
        helpQueue.add(head);

        while (!helpQueue.isEmpty()) {

            // 弹出当前节点，为当前节点构建左右孩子节点
            Node node = helpQueue.poll();
            node.left = generateNode(queues.poll());
            node.right = generateNode(queues.poll());

            if (node.left != null) {
                helpQueue.add(node.left);
            }

            if (node.right != null) {
                helpQueue.add(node.right);
            }
        }

        return head;
    }


    /**
     * 按层遍历序列化
     *
     * @param head
     * @return
     */
    private static Queue<Integer> serializeByLayer(Node head) {

        Queue<Integer> results = new LinkedList<>();
        if (head == null) {
            return results;
        }

        // 添加头结点值
        results.add(head.value);

        // 帮助队列
        Queue<Node> helpQueue = new LinkedList<>();
        helpQueue.add(head);

        while (!helpQueue.isEmpty()) {

            // 弹出队列元素
            Node poll = helpQueue.poll();
            if (poll.left != null) {
                helpQueue.add(poll.left);
                // 添加弹出节点的左孩子节点值
                results.add(poll.left.value);
            } else {
                results.add(null);
            }
            if (poll.right != null) {
                helpQueue.add(poll.right);
                // 添加弹出节点的右孩子节点值
                results.add(poll.right.value);
            } else {
                results.add(null);
            }
        }

        return results;
    }

    /**
     * 按层遍历（重要模板代码）
     * <p>
     * 思路理解：
     * 知识点1：使用队列特性，先进先出。
     * 知识点2：添加节点顺序：
     * - 1. 将头节点添加进队列。
     * - 2. 判断队列是否为空，弹出队列元素（即弹出头结点），再将头结点左孩子节点加进队列，再将头结点右孩子节点加入进队。
     * - 3. 判断队列是否为空，弹出队列元素（即弹出头结点的左孩子结点），再将头结点的左孩子的左孩子结点加进队列，再将头结点的左孩子的右孩子结点加进队列
     * - 4. 以此类推
     *
     * @param head
     */
    private static void layer(Node head) {

        if (head == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            System.out.print(poll.value);
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
    }

    /**
     * 先、中、后遍历（重要模板代码）
     *
     * @param head
     */
    private static void iterate(Node head) {

        if (head == null) {
            return;
        }
        // 先序遍历位置
        System.out.print(head.value + " ");
        iterate(head.left);
        // 中序遍历位置
        iterate(head.right);
        // 后序遍历位置
    }

    /**
     * 创建结点
     *
     * @param value
     * @return
     */
    private static Node generateNode(Integer value) {
        if (value == null) {
            return null;
        }
        return new Node(value);
    }

    static class Node {

        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }

    }

}
